package ds

import (
	"time"
)

type lruinfo struct {
	pos, count int
}

/* head is most frequently used, tail least frequently
 * new entries replace LRU and bubble towards tail */
type LRUQueue struct {
	Entries BasicQueue
	info map[string]lruinfo
	last int
}

func NewLRUQueue(n int) *LRUQueue {

	return &LRUQueue{make(BasicQueue, n), make(map[string]lruinfo), 0}
}

func (q *LRUQueue) bubbledown(i int) {

	entryi := q.Entries[i]
	counti := q.info[entryi.String].count

	for j := i + 1; j < len(q.Entries); j++ {
		strj := q.Entries[j].String
		countj := q.info[strj].count

		if countj <= counti {
			q.Entries[j - 1] = q.Entries[j]
			q.Entries[j] = entryi
			q.info[entryi.String] = lruinfo{pos:j, count:counti}
			q.info[strj] = lruinfo{pos:j-1, count:countj}
		}
	}
}

func (q *LRUQueue) bubbleup(i int) {

}

func (q *LRUQueue) Add(word string, at time.Time) {

	now := time.Now()

	info, ok := q.info[word]
	i := info.pos

	if !ok {
		// new entry, replace LRU entry

		j := 0
		oldest := now
		var zero time.Time

		// find oldest entry; not necessarily near tail
		for i := 0; i < len(q.Entries); i++ {
			if q.Entries[i].Time.Before(oldest) || q.Entries[i].Time == zero {
				oldest = q.Entries[i].Time
				j = i
			}
		}

		entry := QueueEntry{q.last, word, at}
		q.last++
		delete (q.info, q.Entries[j].String)
		q.Entries[j] = entry
		q.info[word] = lruinfo{pos:j, count:1}

		// new entry has count = 0, so bubble to bottom of queue
		q.bubbledown(j)
	} else {
		// update existing entry

		q.Entries[i].Time = at
		infoi := q.info[q.Entries[i].String]
		infoi.count++
		q.info[q.Entries[i].String] = infoi
		q.bubbleup(i)
	}
}

func (q *LRUQueue) At(i int) (string, time.Time, error) {

	return q.Entries[i].String, q.Entries[i].Time, nil
}

func (q *LRUQueue) SinceTime(t time.Time) (res BasicQueue) {

	for i := 0; i < len(q.Entries); i++ {
		if q.Entries[i].Time.After(t) {
			res = append(res, q.Entries[i])
		}
	}

	return
}

func (q *LRUQueue) Since(id int) (res BasicQueue) {

	for i := 0; i < len(q.Entries); i++ {
		if q.Entries[i].Index > id {
			res = append(res, q.Entries[i])
		}
	}

	return
}

